//
// Created by Luhang on 2023/5/28/028.
//

#ifndef INC_0513_HASHTABLE_H
#define INC_0513_HASHTABLE_H

#endif //INC_0513_HASHTABLE_H

#pragma once

#include <vector>
#include <iostream>
using namespace std;


template<class K>
struct HashFunc{
    size_t operator()(const K& key){
        return key;
    }
};

template<>
struct HashFunc<string>{
    size_t operator()(const string& s){
        size_t hash = 0;
        for (auto ch : s) {
            hash += ch;
            hash *= 31;
        }
        return hash;
    }
};


namespace HashBucket{
    template<class T>
    struct HashNode{
        HashNode<T>* _next;
        T _data;

        HashNode(const T& data)
                : _next(nullptr)
                , _data(data)
        {}
    };

    template<class K, class T, class KeyOfT, class Hash>
    class HashTable;

    template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
    struct __HashIterator{
        typedef HashNode<T> Node;
        typedef HashTable<K, T, KeyOfT, Hash> HT;
        typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
        typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;

        Node* _node;
        const HT* _ht;

        __HashIterator(Node* node, const HT* ht)
        :_node(node)
        ,_ht(ht)
        {}

        __HashIterator(const Iterator& it)
        :_node(it._node)
        ,_ht(it._ht)
        {}

        Ref operator*(){
            return _node->_data;
        }

        Ptr operator->(){
            return &(_node->_data);
        }

        bool operator!=(const Self& s){
            return _node != s._node;
        }

        Self& operator++(){
            if (_node->_next != nullptr)
                _node = _node->_next;
            else{
                KeyOfT kot;
                Hash hash;
                size_t hashI = hash(kot(_node->_data)) % _ht->_tables.size();
                ++hashI;
                while (hashI < _ht->_tables.size()){
                    if (_ht->_tables[hashI]){
                        _node = _ht->_tables[hashI];
                        break;
                    } else
                        ++hashI;
                }
                if (hashI == _ht->_tables.size())
                    _node = nullptr;
            }
            return *this;
        }

/*
        Self& operator++(){
            if (_node->_next != nullptr)
                _node = _node->_next;
            else{
                KeyOfT kot;
                Hash hash;
                size_t hashI = hash(kot(_node->_data)) % _ht->_tables.size();
                ++hashI;
                while (hashI < _ht->_tables.size()){
                    if (_ht->_tables[hashI]){
                        _node = _ht->_tables[hashI];
                        break;
                    }else
                        ++hashI;
                }
                if (hashI == _ht->_tables.size())
                    _node = nullptr;
            }
            return *this;
        }
*/

    };


    template<class K, class T, class KeyOfT, class Hash>
    class HashTable{
        typedef HashNode<T> Node;

/*        template<typename K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
        friend struct __HashIterator;*/

    private:
        size_t _n = 0;
    public:

        typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
        typedef __HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;

        iterator begin(){
            Node* cur = nullptr;
            for (int i = 0; i < _tables.size(); ++i) {
                cur = _tables[i];
                if (cur)
                    break;
            }
            return iterator(cur, this);
        }

        iterator end(){
            return iterator(nullptr, this);
        }

        const_iterator begin()const{
            Node* cur = nullptr;
            for (int i = 0; i < _tables.size(); ++i) {
                cur = _tables[i];
                if (cur)
                    break;
            }
            return const_iterator(cur, this);
        }

        const_iterator end()const{
            return const_iterator(nullptr, this);
        }

        ~HashTable(){
            for (auto& cur : _tables) {
                while (cur){
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                cur = nullptr;
            }
        }

        iterator Find(const K& key){
            if (_tables.size() == 0)
                return end();

            KeyOfT kot;
            Hash hash;
            size_t hashI = hash(key) % _tables.size();
            Node* cur = _tables[hashI];
            while (cur){
                if (kot(cur->_data) == key)
                    return iterator(cur, this);
                cur = cur->_next;
            }
            return end();
        }

        bool Erase(const K& key){
            KeyOfT kot;
            Hash hash;
            size_t hashI = hash(key) % _tables.size();
            Node* cur = _tables[hashI];
            Node* prev = nullptr;
            while (cur){
                if (kot(cur->_data) == key){
                    if (prev == nullptr)
                        _tables[hashI] = cur->_next;
                    else
                        prev->_next = cur->_next;
                    delete cur;
                    return true;
                } else{
                    prev = cur;
                    cur =  cur->_next;
                }
            }
            return false;
        }

        pair<iterator, bool> Insert(const T& data){
            KeyOfT kot;
            Hash hash;

            iterator it = Find(kot(data));
            if (it != end())
                return make_pair(it, false);

            if (_n == _tables.size()){
                size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
                vector<Node*> newTables(newSize, nullptr);
                for (auto& cur : _tables) {
                    while (cur){
                        Node* next = cur->_next;
                        size_t hashI = hash(kot(cur->_data)) % newTables.size();

                        cur->_next = newTables[hashI];
                        newTables[hashI] = cur;
                        cur = next;
                    }
                }
                _tables.swap(newTables);
            }

            size_t hashI = hash(kot(data)) % _tables.size();
            Node* newNode = new Node(data);
            newNode->_next = _tables[hashI];
            _tables[hashI] = newNode;

            ++_n;
            return make_pair(iterator(newNode, this), true);
        }

        vector<Node*> _tables;
    };

}